% This is a simple Turing Machine written in prolog.
% To call, use 
% compute(+Transit, +BeginState, -Output)
% where Transit is a transition-predicate as detailed
% at the end of the file.
% The two- and threebeaver are provided as examples.

% for comments and questions contact gpickard _AT_ uos _DOT_ de
% (c) 2008 Gabriel Pickard. Thanx to Stefan Schneider for
% his inspiration.


% move(+Direction, +Left, +Right, -NewLeft, -NewRight)
% Moves the tape-representation in given Direction.
move(left, [Val | Left], Right, Left, [Val | Right]).
move(right, Left, [Val | Right], [Val | Left], Right).

% ground_val(+Val)
% Grounds our tape-values, to 0 if need be.
ground_val(Val):-
	ground(Val), !.
ground_val(0).

% state(+Left, +Right, +State, -OutLeft, -OutRight)
% goes through actual state-transitions. Returns final state of tape.
state(_,Left,Right,terminal, Left, Right).
state(Transit, [Val | Left], Right, State, OutLeft, OutRight):-
	ground_val(Val),
	call(Transit, State, Val, Write, Dir, NewState),
	move(Dir, [Write |Left], Right, NewLeft, NewRight),
	state(Transit, NewLeft, NewRight, NewState, OutLeft, OutRight).

% groundify_list(+L)
% Used to return pretty output list.
groundify_list([]):- !.
groundify_list([H |T]):-
	groundify_list(T).	


% compute(+Transit, +BeginState, -Out)
% Computes the output of a given Machine (represented by transit).
% Make sure your machine halts!
compute(Transit, BeginState, Out):-
	state(Transit,_,_, BeginState, OutLeft, OutRight),
	reverse(OutLeft, LeftRev), !,
	append(LeftRev, OutRight, Out),
	groundify_list(Out).


% Transition-predicates should encoded be as follows:
% transit(State, InValue, Write, Direction, NewState)

% the terminal/halting state is called 'terminal' but you can
% change this if you like. (Alter the first clause of the predicate state.)
% You can also change the default value of the tape by changing the second
% clause in ground_val/1

twobeaver(a,0,1,right,b).
twobeaver(a,1,1,left,b).
twobeaver(b,0,1,left,a).
twobeaver(b,1,1,right,terminal).


threebeaver(a,0,1,right,b).
threebeaver(b,0,0,right,c).
threebeaver(c,0,1,left,c).
threebeaver(a,1,1,right,terminal).
threebeaver(b,1,1,right,b).
threebeaver(c,1,1,left,a).

